Dự án OpenStreetMap được sáng lập vào tháng 7 năm 2004, khi người Anh Steve Coast đi xe đạp chung quanh Công viên Nhiếp chính (Regent's Park) ở Luân Đôn với máy thu GPS và nhập dữ liệu vào máy tính xách tay, vì cơ quan bản đồ quốc gia Ordnance Survey lúc đó đòi tiền cho các bản đồ và lớp vectơ cơ bản.[4] Quỹ OpenStreetMap được thành lập vào tháng 4 năm 2006. Hội nghị quốc tế OpenStreetMap, "The State of the Map", được tổ chức vào tháng 7 năm 2007; lúc đó dự án có 9.000 thành viên đăng ký. Các công ty bảo trợ bao gồm Google, Yahoo!, và Multimap.com.

Tháng 12 năm 2006, Yahoo! xác nhận rằng những người đóng góp OpenStreetMap có quyền vẽ bản đồ theo hình từ không trung của Yahoo! Maps API để thay thế hình ảnh mờ hơn của vệ tinh Landsat.[19] Yahoo! ngừng dịch vụ này ngày 13 tháng 9 năm 2011,[20] nhưng trước đó Microsoft đã cho phép sử dụng hình từ không trung của Bing Maps.[21]

OpenStreetMap đôi khi nhập thông tin địa lý từ các cơ sở dữ liệu khác để tăng tốc độ phát triển của dự án. Vào tháng 4 năm 2007, Automotive Navigation Data (AND) đóng góp một cỡ sở dữ liệu có mạng lưới đường sá đầy đủ tại Hà Lan và các đường chính tại Ấn Độ và Trung Quốc.[22] Bản đồ vẫn còn nghiêng về Tây Âu, nơi ở của những người đóng góp đầu tiên, cho nên vào tháng 10 năm đó OpenStreetMap hoàn thành nhập cơ sở dữ liệu đường sá TIGER của Điều tra dân số Hoa Kỳ.[23]

Vào những ngày sau động đất Haiti 2010, cộng đồng OpenStreetMap cùng với Crisis Commons vội vàng cải tiến bản đồ Haiti dùng hình vệ tinh và phân phối dữ liệu cho các tổ chức cứu tế để sử dụng trong máy thu GPS trong việc tìm kiếm cứu nạn.[24] Họ thành lập một tổ chức phi chính phủ, Humanitarian OpenStreetMap Team (HOT), để cung cấp thông tin địa lý sau các tai nạn lớn tại nước nghèo.[25]

Tháng 2 năm 2009, nhóm hoạt động Giấy phép của Quỹ OpenStreetMap chính thức đề nghị đổi giấy phép của cơ sở dữ liệu từ Creative Commons Ghi công–Chia sẻ tương tự (CC BY-SA) 2.0 qua Giấy phép Cơ sở dữ liệu Mở (ODbL) 1.0,[26] với mục đích làm rõ tình trạng của dữ liệu trong cơ sở dữ liệu và để chắc chắn hơn về việc bảo vệ dữ liệu khỏi bị sao chép trái phép.[27] Cộng đồng biểu quyết tán thành việc chuyển đổi cơ sở dữ liệu vào tháng 12.[28] Vào những năm sau, OpenStreetMap yêu cầu mọi người đóng góp tán thành các điều khoản đóng góp mới, bao gồm giấy phép mới. Những đóng góp của người phản đối hoặc không trả lời bị ẩn (redacted) vào tháng 7 năm 2012.[29] Thay đổi này gây ra nhiều tranh luận trong cộng đồng. Một số thành viên bỏ cộng đồng và tách ra dự án FOSM để tiếp tục sử dụng CC BY-SA, trong khi một số thành viên tiếp tục tham gia OpenStreetMap nhưng tuyên bố rằng các đóng góp của họ thuộc phạm vi công cộng.[15] Vào ngày 12 tháng 9 năm 2012, dự án hoàn thành quá trình chuyển đổi cơ sở dữ liệu qua ODbL.[30]